package m_HashTable;

import java.util.Map;
import java.util.TreeMap;
 
public class HashTable_0<K extends Comparable<K>, V> {      //BUG 由于我们底层复用了TreeMap(红黑树实现)，所以K是要求可比较性的，否则会有bug；
								//在Java8之前，HashTable解决hash冲突复用的是链表，所以不用限制K的可比较性；但在Java8之后进行了优化，底层先是复用链表，等链表长度达到阈值，就转为红黑树结构来提高效率；
										//所以其机制就是：如果K是可比的，达到阈值就自动转RBTree； 如果不可比，就按Java8之前 即一直使用链表；
    private static final int upperTol = 10;  //upper tolerance  是对hash冲突的容忍度
    private static final int lowerTol = 2;
    private static final int initCapacity = 7; //最小容量 缩容的极限

    private TreeMap<K, V>[] hashtable;
    private int size;
    private int M;

    public HashTable_0(int M){
        this.M = M;
        size = 0;
        hashtable = new TreeMap[M];
        for(int i = 0 ; i < M ; i ++)
            hashtable[i] = new TreeMap<>();
    }

    public HashTable_0(){
        this(initCapacity);
    }

    private int hash(K key){
        return (key.hashCode() & 0x7fffffff) % M;
    }

    public int getSize(){
        return size;
    }

    public void add(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key))
            map.put(key, value);
        else{
            map.put(key, value);
            size ++;

            if(size >= upperTol * M)    //hash冲突是否严重 应该看整体情况平均情况
                resize(2 * M);
        }
    }

    public V remove(K key){
        V ret = null;
        TreeMap<K, V> map = hashtable[hash(key)];
        if(map.containsKey(key)){
            ret = map.remove(key);
            size --;
            										//增补
            if(size < lowerTol * M && M / 2 >= initCapacity)    //缩容一方面可以减少空间的浪费，因为空间和时间往往达到一个临界平衡点的时候，再增加空间 其带来的时间收益就甚微了，成本考虑 也就没必要了；
                resize(M / 2);								// 其次是，hash(key)的分布是否够均匀够松散 和hash函数是直接相关的，所以空间的增加 也有可能带不来时间的收益； 所以扩容缩容时的取值是很关键的；
        }
        return ret;
    }

    public void set(K key, V value){
        TreeMap<K, V> map = hashtable[hash(key)];
        if(!map.containsKey(key)) 
            throw new IllegalArgumentException(key + " doesn't exist!");

        map.put(key, value);
    }

    public boolean contains(K key){
        return hashtable[hash(key)].containsKey(key);
    }

    public V get(K key){
        return hashtable[hash(key)].get(key);
    }

    private void resize(int newM){   	//增补的resize特性，因为当数据规模太大时，hash冲突不可避免的基数过大，此时扩容的话对于长远的综合效率来说 是更有利的，因为扩容是一次性的，而每次操作的效率提升是长久的；
        TreeMap<K, V>[] newHashTable = new TreeMap[newM];
        for(int i = 0 ; i < newM ; i ++)
            newHashTable[i] = new TreeMap<>();

        int oldM = M;
        this.M = newM;
        for(int i = 0 ; i < oldM ; i ++){
            TreeMap<K, V> map = hashtable[i];
            for(K key: map.keySet())
                newHashTable[hash(key)].put(key, map.get(key));
        }

        this.hashtable = newHashTable;			
    }
}																			//扩容缩容时的取值是很关键的，此版本尚待改进；
